home *** CD-ROM | disk | FTP | other *** search
- /*****************************************************************************/
- /* File : SORT.C Copyright (c) 1992 */
- /* */
- /* Author : Kenneth W. Hartlen */
- /* Address : Box 37, Site 6, RR#3 */
- /* Armdale, Nova Scotia */
- /* B3L 4J3 Canada */
- /* */
- /* Purpose : Simple program that uses graphics commands and can be */
- /* be compiled in Lattice C, Sozobon C and Turbo C. */
- /* */
- /* This programs show, graphically, how the bubble sort, */
- /* insertion sort, selection sort and quick sort work. */
- /* */
- /* Insertion sort and selection sort algorithms from: */
- /* "Data Structures and Progam Design", Robert L. Kruse */
- /* */
- /* Quick sort algorithm from: */
- /* "The C Programming Language", 2nd Ed., Kernighan & Ritchie */
- /*****************************************************************************/
- /* Compiling with Lattice C: */
- /* lc.ttp -fm sort.c */
- /* clink.ttp c.o+sort.o */
- /* LIB graphics.lib+lcm.lib+lcg.lib+lc.lib */
- /* TO sort.prg */
- /* */
- /* Compiling with Sozobon C: */
- /* cc -c sort.c */
- /* cc -o sort.prg -r sort.o graphics.a aesfast.a vdifast.a */
- /* */
- /* Compiling with Heat & Serve Sozobon C v1.33i: */
- /* cc -c lines.c */
- /* cc -o lines.prg lines.o graphics.a libm.a aesfast.a \ */
- /* vdifast.a */
- /* */
- /* Compile with Turbo C: */
- /* Use Turbo C's IDE */
- /* */
- /*****************************************************************************/
-
- #ifdef SOZOBON
- #define __MAIN_SRC__ /* to be included with user's source */
- #endif
-
- #include <stdio.h> /* common header files */
- #include <graphics.h>
-
- #ifndef SOZOBON /* includes for Lattice and Turbo */
- #include <stdlib.h>
- #include <dos.h>
- #endif
-
- #ifndef __TURBOC__ /* includes for Lattice and Sozobon */
- #include <osbind.h>
- #endif
-
- /*****************************************************************************/
- /* Main program loop */
- /*****************************************************************************/
-
- #define NUMPOINTS 100 /* maximum # of lines to display */
-
- int maxX, /* save getmaxx() result */
- maxY, /* save getmaxy() result */
- numcolours,
- width,
- points[NUMPOINTS], /* array holding values */
- seed; /* random number seed */
-
- #ifdef __TURBOC__
- struct time now;
- #endif
-
- /*****************************************************************************/
- /* Function prototypes */
- void build_list();
- void display_graph();
- void update_graph();
- void pause();
-
- int maxkey();
- void swap();
-
- void bubble_sort();
- void insertion_sort();
- void selection_sort();
-
- void q_sort();
- void quick_sort();
-
- /*****************************************************************************/
- void main()
- {
- int graphdriver = DETECT, graphmode;
-
-
- /* initialize graphics */
- initgraph(&graphdriver,&graphmode,"");
-
- maxX = getmaxx(); /* save values to eliminate */
- maxY = getmaxy() - textheight("H"); /* function call in the do loop */
- numcolours = getmaxcolor();
- width = maxX / NUMPOINTS;
-
- /* Display Title screen */
- setcolor(WHITE);
- settextjustify(CENTER_TEXT,TOP_TEXT);
- outtextxy(maxX/2,maxY/3,"SORT DEMO");
- outtextxy(maxX/2,maxY/3+textheight("H")*2,"by Kenneth W. Hartlen");
- outtextxy(maxX/2,maxY/3+textheight("H")*4,"Copyright (c) 1992");
- outtextxy(maxX/2,maxY/3+textheight("H")*7,"press a key to continue");
- rectangle(0,0,maxX,maxY);
- getch();
-
- /* initialize variables */
- #ifdef __TURBOC__ /* get system time for use as the */
- gettime(&now); /* random number generator seed */
- seed = now.ti_sec;
- #else
- seed = Tgettime();
- #endif
-
- build_list(seed,points,NUMPOINTS);
- display_graph(points,NUMPOINTS,"Bubble Sort");
- bubble_sort(points,NUMPOINTS);
- pause("Press any key to continue...");
-
- build_list(seed,points,NUMPOINTS);
- display_graph(points,NUMPOINTS,"Insertion Sort");
- insertion_sort(points,NUMPOINTS);
- pause("Press any key to continue...");
-
- build_list(seed,points,NUMPOINTS);
- display_graph(points,NUMPOINTS,"Selection Sort");
- selection_sort(points,NUMPOINTS);
- pause("Press any key to continue...");
-
- build_list(seed,points,NUMPOINTS);
- display_graph(points,NUMPOINTS,"Quick Sort");
- quick_sort(points,NUMPOINTS);
- pause("Demo finished. Press any key...");
-
- closegraph(); /* close graphics */
- return;
-
- } /* main */
-
- /*****************************************************************************/
- /* Generate a list of random number to sort */
- void build_list(seed, points, num)
- int seed, points[], num;
- {
- int i;
-
- srand(seed);
- for(i=0;i<num;i++)
- points[i] = rand() % maxY;
-
- }
-
- /*****************************************************************************/
- /* Display a graph of the list */
- void display_graph(points, num, name)
- int points[], num;
- char *name;
- {
- int i,pat,col;
-
- cleardevice();
- rectangle(0,0,(width*num)+2,maxY);
- settextjustify(LEFT_TEXT,TOP_TEXT);
- outtextxy(0,maxY+1,"0");
- outtextxy( (width*num)-textwidth("99"),maxY+1,"99");
- settextjustify(CENTER_TEXT,TOP_TEXT);
- outtextxy((width*num)/2,maxY+1,name);
-
- for(i=0;i<num;i++) {
- if (numcolours == 1) {
- pat=((points[i] * 12) / maxY ) + 1;
- setfillstyle(pat,WHITE);
- }
- else {
- col=((points[i] * numcolours) / maxY ) + 1;
- setfillstyle(SOLID_FILL,col);
- }
- bar((i*width)+1,maxY-points[i],((i+1)*width)-1,maxY);
- }
-
- }
-
- /*****************************************************************************/
- /* Update the graph */
- void update_graph(points, i)
- int points[], i;
- {
- int pat,col;
-
- if (numcolours == 1) {
- pat=((points[i] * 12) / maxY ) + 1;
- setfillstyle(pat,WHITE);
- }
- else {
- col=((points[i] * numcolours) / maxY ) + 1;
- setfillstyle(SOLID_FILL,col);
- }
- bar((i*width)+1,maxY-points[i],((i+1)*width)-1,maxY);
-
- setfillstyle(SOLID_FILL, BLACK);
- bar((i*width)+1,1,((i+1)*width)-1,maxY-points[i]-1);
-
- }
-
- /*****************************************************************************/
- /* Wait for user to press a key */
-
- void pause(msg)
- char *msg;
- {
- settextjustify(CENTER_TEXT,TOP_TEXT);
- outtextxy(maxX/2,10,msg);
- getch();
- }
-
- /*****************************************************************************/
- /* Various support functions for sort routines */
- int maxkey(L, low, high)
- int L[], low, high;
- {
- int m,j;
-
- m = low;
- for (j=low+1;j<=high;j++) {
- if (L[m] < L[j])
- m = j;
- }
- return m;
-
- }
-
- void swap(L, x, y)
- int L[], x, y;
- {
- int t;
-
- t = L[x];
- L[x] = L[y];
- L[y] = t;
- update_graph(L,x);
- update_graph(L,y);
-
- }
-
- /*****************************************************************************/
- /* Perform a bubble sort on the list */
- void bubble_sort(L, n)
- int L[], n;
- {
- int i,j;
-
- for (i=0;i<n;i++)
- for (j=i+1;j<n;j++)
- if (L[i] > L[j])
- swap(L,i,j);
-
- }
-
- /*****************************************************************************/
- /* Perform an insertion sort on the list */
- void insertion_sort(L, n)
- int L[], n;
- {
- int i,j,found,t;
-
- for(i=1;i<n;i++) {
- if (L[i] < L[i-1]) {
- j = i;
- t = L[i];
- do {
- j = j - 1;
- L[j+1] = L[j];
- update_graph(L,j+1);
- if (j==0)
- found = 1;
- else
- found = (L[j-1] <= t);
- } while (!found);
- L[j] = t;
- update_graph(L,j);
- }
- }
-
- }
-
- /*****************************************************************************/
- /* Perform a selection sort on the list */
- void selection_sort(L, n)
- int L[], n;
- {
- int i,m;
-
- for(i=n-1;i>=1;i--) {
- m = maxkey(L,0,i);
- swap(L,m,i);
- }
- }
-
- /*****************************************************************************/
- /* Perform a quick sort on the list */
- void quick_sort(points, num)
- int points[], num;
- {
- q_sort(points,0,num-1);
- }
-
- void q_sort(v, left, right)
- int v[], left, right;
- {
- int i,last;
-
- if (left >= right)
- return;
-
- swap(v,left,right);
- last = left;
- for (i=left+1;i<=right;i++)
- if (v[i] < v[left])
- swap(v,++last,i);
- swap(v,left,last);
- q_sort(v,left,last-1);
- q_sort(v,last+1,right);
-
- }
-
-